{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Divide Players Into Teams of Equal Skill"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: dividePlayers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #划分技能点相等的团队"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组 <code>skill</code> ，数组长度为 <strong>偶数</strong> <code>n</code> ，其中 <code>skill[i]</code> 表示第 <code>i</code> 个玩家的技能点。将所有玩家分成 <code>n / 2</code> 个 <code>2</code> 人团队，使每一个团队的技能点之和 <strong>相等</strong> 。</p>\n",
    "\n",
    "<p>团队的 <strong>化学反应</strong> 等于团队中玩家的技能点 <strong>乘积</strong> 。</p>\n",
    "\n",
    "<p>返回所有团队的 <strong>化学反应</strong> 之和，如果无法使每个团队的技能点之和相等，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>skill = [3,2,5,1,3,4]\n",
    "<strong>输出：</strong>22\n",
    "<strong>解释：</strong>\n",
    "将玩家分成 3 个团队 (1, 5), (2, 4), (3, 3) ，每个团队的技能点之和都是 6 。\n",
    "所有团队的化学反应之和是 1 * 5 + 2 * 4 + 3 * 3 = 5 + 8 + 9 = 22 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>skill = [3,4]\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>\n",
    "两个玩家形成一个团队，技能点之和是 7 。\n",
    "团队的化学反应是 3 * 4 = 12 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>skill = [1,1,2,3]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>\n",
    "无法将玩家分成每个团队技能点都相等的若干个 2 人团队。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= skill.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>skill.length</code> 是偶数</li>\n",
    "\t<li><code>1 &lt;= skill[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [divide-players-into-teams-of-equal-skill](https://leetcode.cn/problems/divide-players-into-teams-of-equal-skill/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [divide-players-into-teams-of-equal-skill](https://leetcode.cn/problems/divide-players-into-teams-of-equal-skill/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,5,1,3,4]', '[3,4]', '[1,1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      n = len(skill)\n",
    "      div, mod = divmod(sum(skill), (n // 2))\n",
    "      if mod:\n",
    "        return -1\n",
    "\n",
    "      if max(skill) >= div:\n",
    "        return -1\n",
    "      \n",
    "      mp = collections.defaultdict(int)\n",
    "\n",
    "      res = 0\n",
    "      for s in skill:\n",
    "        if div - s in mp:\n",
    "            res += s * (div - s)\n",
    "            mp[div - s] -= 1\n",
    "            if mp[div - s] == 0:\n",
    "              del mp[div - s]\n",
    "        else:\n",
    "            mp[s] += 1\n",
    "        \n",
    "      if len(mp):\n",
    "        return -1\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        s = sum(skill)\n",
    "        n = len(skill)\n",
    "        if s%(n//2)!=0:return -1\n",
    "        ss = s//(n//2)\n",
    "        ans = 0\n",
    "        cnt = Counter(skill)\n",
    "        for x in skill:\n",
    "            if x in cnt and cnt[x]>0:\n",
    "                y = ss - x\n",
    "                cnt[x]-=1\n",
    "\n",
    "                if y in cnt and cnt[y]>0:\n",
    "                    ans+=x*y\n",
    "                    cnt[y]-=1\n",
    "                else:\n",
    "                    return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      l, h = 1000, 0\n",
    "      n = len(skill)\n",
    "      s, m = 0, {}\n",
    "      d = set()\n",
    "      for x in skill:\n",
    "        s += x\n",
    "        d.add(x)\n",
    "        if x not in m:\n",
    "          m[x] = 1\n",
    "        else:\n",
    "          m[x] += 1\n",
    "        if x < l:\n",
    "          l = x\n",
    "        if x > h:\n",
    "          h = x\n",
    "      if n // 2 * (l + h) != s:\n",
    "        return -1\n",
    "      ans = 0\n",
    "      x = l\n",
    "      while x <= (l + h) // 2:\n",
    "        if x in d:\n",
    "          if x * 2 == (l + h):\n",
    "            if m[x] % 2 == 0:\n",
    "              ans += (x * x * (m[x] // 2))\n",
    "            else:\n",
    "              return -1\n",
    "          elif m[x] == m[l + h - x]:\n",
    "            ans += (x * (l + h - x) * m[x])\n",
    "          else:\n",
    "            return -1\n",
    "        x += 1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        sum=0\n",
    "        n=len(skill)\n",
    "        if n==2:\n",
    "            return skill[0]*skill[1]\n",
    "        t=skill[n//2-1]+skill[n//2]\n",
    "        for i in range(n//2):\n",
    "            if skill[i]+skill[n-i-1]!=t:\n",
    "                return -1\n",
    "            else:\n",
    "                sum+=skill[i]*skill[n-i-1]\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        lengh = len(skill)\n",
    "        if lengh == 2:\n",
    "            return skill[0] * skill[1]\n",
    "        else:\n",
    "            # 先排序。然后依次取头尾和。\n",
    "            # 如果从第二对开始不等于头尾和。则退出返回 -1\n",
    "            skill.sort()\n",
    "\n",
    "            tmp = skill[0] +skill[-1]\n",
    "            res = 0\n",
    "\n",
    "            for i in range(lengh // 2):\n",
    "                start = skill[i]\n",
    "                end = skill[-1 - i]\n",
    "                if start + end == tmp:\n",
    "                    res += start * end\n",
    "                else:\n",
    "                    return -1\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        i,j = 0, len(skill)-1\n",
    "        total = skill[i]+skill[j]\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if skill[i]+skill[j] == total:\n",
    "                res+=skill[i]*skill[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "                continue\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      skill.sort()\n",
    "\n",
    "      sum_ = skill[0] + skill[-1]\n",
    "\n",
    "      i = 1\n",
    "      j = len(skill) - 2\n",
    "\n",
    "      res = skill[0] * skill[-1]\n",
    "      while i < j:\n",
    "        if skill[i] + skill[j] != sum_:\n",
    "          return -1\n",
    "\n",
    "        res += skill[i] * skill[j]\n",
    "        i += 1\n",
    "        j -= 1\n",
    "      \n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        total, m = sum(skill), len(skill) // 2\n",
    "        if total % m: return -1\n",
    "        skill.sort()\n",
    "        i,j = 0, len(skill)-1\n",
    "        total = skill[i]+skill[j]\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if skill[i]+skill[j] == total:\n",
    "                res+=skill[i]*skill[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "                continue\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      total, m = sum(skill), len(skill) // 2\n",
    "      if total % m:\n",
    "        return -1\n",
    "      ans, s = 0, total // m\n",
    "      cnt = Counter(skill)\n",
    "      for x, c in cnt.items():\n",
    "        if c != cnt[s - x]:\n",
    "          return -1\n",
    "        ans += c * x * (s - x)\n",
    "      return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        i,j = 0, len(skill)-1\n",
    "        total = skill[i]+skill[j]\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if skill[i]+skill[j] == total:\n",
    "                res+=skill[i]*skill[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "                continue\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        count=(len(skill)+1)//2\n",
    "        skill_tep=sorted(skill)\n",
    "        skillnum=min(skill)+max(skill)\n",
    "        ans=0\n",
    "        for i in range(count):\n",
    "            if skill_tep[i]+ skill_tep[len(skill)-1-i]!=skillnum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans=ans+skill_tep[i]*skill_tep[len(skill)-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        t = skill[0] + skill[-1]\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        r = len(skill) - 1\n",
    "        while l < r:\n",
    "            if t != skill[l] + skill[r]:\n",
    "                return -1\n",
    "            ans += skill[l] * skill[r]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n = len(skill)\n",
    "        total = sum(skill)\n",
    "        cnt = n//2\n",
    "        target = total//cnt\n",
    "        ans = 0\n",
    "        record = Counter(skill)\n",
    "        for k in list(record.keys()):\n",
    "            if k >= target:\n",
    "                return -1\n",
    "            v = record[k]\n",
    "            if v == 0:\n",
    "                continue\n",
    "            t = target-k\n",
    "            if t == k:\n",
    "                if v&1:\n",
    "                    return -1\n",
    "                ans += k*k*(v//2)\n",
    "            else:\n",
    "                if record[t] < v:\n",
    "                    return -1\n",
    "                record[t] -= v\n",
    "                ans += k*t*v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      l, h = 1000, 0\n",
    "      n = len(skill)\n",
    "      s, m = 0, {}\n",
    "      for x in skill:\n",
    "        s += x\n",
    "        if x not in m:\n",
    "          m[x] = 1\n",
    "        else:\n",
    "          m[x] += 1\n",
    "        if x < l:\n",
    "          l = x\n",
    "        if x > h:\n",
    "          h = x\n",
    "      if n // 2 * (l + h) != s:\n",
    "        return -1\n",
    "      ans = 0\n",
    "      x = l\n",
    "      while x <= (l + h) // 2:\n",
    "        if x in m:\n",
    "          if x * 2 == (l + h):\n",
    "            if m[x] % 2 == 0:\n",
    "              ans += (x * x * (m[x] // 2))\n",
    "            else:\n",
    "              return -1\n",
    "          elif m[x] == m[l + h - x]:\n",
    "            ans += (x * (l + h - x) * m[x])\n",
    "          else:\n",
    "            return -1\n",
    "        x += 1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        target = skill[0] + skill[-1]\n",
    "        ans = 0\n",
    "        for i in range(len(skill) >> 1):\n",
    "            if skill[i] + skill[-1-i] != target:\n",
    "                return -1\n",
    "            ans += skill[i] * skill[-1-i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      ans=0\n",
    "      d={}\n",
    "      tot=0\n",
    "      for i in skill:\n",
    "        tot+=i\n",
    "        if i in d:\n",
    "          d[i]+=1\n",
    "        else:\n",
    "          d[i]=1\n",
    "      s=2*tot//len(skill)\n",
    "      if 2*tot%(len(skill))!=0:\n",
    "        return -1\n",
    "      for i in d:\n",
    "        if not s-i in d or d[i]!=d[s-i]:\n",
    "          return -1\n",
    "        ans+=d[i]*i*(s-i)\n",
    "      return ans//2\n",
    "      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        total, m = sum(skill), len(skill) // 2\n",
    "        if total % m: return -1\n",
    "        ans, s = 0, total // m\n",
    "        cnt = Counter(skill)\n",
    "        for x, c in cnt.items():\n",
    "            if c != cnt[s - x]: return -1\n",
    "            ans += c * x * (s - x)\n",
    "        return ans // 2\n",
    "'''\n",
    "作者：灵茶山艾府\n",
    "链接：https://leetcode.cn/problems/divide-players-into-teams-of-equal-skill/solutions/2005108/pai-xu-hou-zui-xiao-zui-da-pi-pei-by-end-7sta/\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        n = len(skill)\n",
    "        left, right =0, n-1\n",
    "        ans = 0\n",
    "        temp_sum = sum(skill) // (n//2)\n",
    "\n",
    "        while left < right:\n",
    "            if skill[left] + skill[right] != temp_sum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans += skill[left] * skill[right]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        s = sum(skill)\n",
    "        teams = len(skill) // 2\n",
    "        if s % teams: return -1\n",
    "        cnt = Counter(skill)\n",
    "        total = s // teams\n",
    "        ans = 0\n",
    "        for a in cnt.keys():\n",
    "            if cnt[total - a] != cnt[a]:\n",
    "                return -1\n",
    "            ans += a * (total - a) * cnt[a]\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        sum = 0\n",
    "        n = len(skill)\n",
    "        if n == 2:return skill[0]*skill[1]\n",
    "        for i in range(1,n//2):\n",
    "            if skill[i] + skill[n-1-i] == skill[0]+skill[n-1]:\n",
    "                sum += (skill[i] * skill[n-1-i])\n",
    "            else:\n",
    "                return -1\n",
    "        return sum + (skill[0]*skill[n-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        ans = 0\n",
    "        skill.sort()\n",
    "        left, right =0, len(skill) - 1\n",
    "        temp = skill[0] + skill[-1]\n",
    "        while left < right:\n",
    "            if skill[left] + skill[right] != temp:\n",
    "                return -1\n",
    "            ans += skill[left] * skill[right]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        # 排序+首尾配对\n",
    "        skill.sort()\n",
    "        sm = 0\n",
    "        n = len(skill)\n",
    "        res = 0\n",
    "        for i in range(n // 2):\n",
    "            cur_sm = skill[i] + skill[n - i - 1]\n",
    "            if sm == 0:\n",
    "                sm = cur_sm\n",
    "            elif sm != cur_sm:\n",
    "                return -1\n",
    "            res += skill[i] * skill[n - i - 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans = 0\n",
    "        n = len(skill)\n",
    "        s = sum(skill) // (n // 2)\n",
    "        for i in range(n // 2):\n",
    "            if s != skill[i] + skill[n-i-1]:\n",
    "                # print(s, i, n-i-1)\n",
    "                return -1\n",
    "            ans += skill[i] * skill[n-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        res = 0\n",
    "        n = len(skill)\n",
    "        s = skill[0] + skill[-1]\n",
    "        for i in range(n // 2):\n",
    "            if skill[i] + skill[n - i - 1] != s:\n",
    "                return -1\n",
    "            res += skill[i] * skill[n - i - 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        i,j = 0, len(skill)-1\n",
    "        total = skill[i]+skill[j]\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if skill[i]+skill[j] == total:\n",
    "                res+=skill[i]*skill[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "                continue\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        target = 2*sum(skill)//len(skill)\n",
    "       \n",
    "        if (2*sum(skill))%len(skill):\n",
    "            return -1\n",
    "        \n",
    "        res= {}\n",
    "        point = 0\n",
    "\n",
    "        for i in skill:\n",
    "            y=target-i\n",
    "            if y in res and res[y]:\n",
    "                res[y]-=1\n",
    "                point+=y*i\n",
    "            else:\n",
    "                if i in res:\n",
    "                    res[i]+=1\n",
    "                else:\n",
    "                    res[i]=1\n",
    "        \n",
    "        for k,v in res.items():\n",
    "            if v:\n",
    "                return -1\n",
    "        return point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        sort_skill = sorted(skill)\n",
    "        tmp = sort_skill[0] + sort_skill[-1]\n",
    "        n = len(skill)\n",
    "        out = 0\n",
    "        for i in range (n // 2):\n",
    "            a, b = sort_skill[i], sort_skill[n-i-1]\n",
    "            if a+b != tmp:\n",
    "                return -1\n",
    "            out += a * b\n",
    "        return out "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        p = 0\n",
    "        q = len(skill)-1\n",
    "        re = 0\n",
    "        su = skill[0] + skill[-1]\n",
    "        while p<q:\n",
    "            if skill[p] + skill[q] != su:\n",
    "                return -1\n",
    "            re += skill[p]*skill[q]\n",
    "            p += 1\n",
    "            q -= 1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        i,j = 0, len(skill)-1\n",
    "        total = skill[i]+skill[j]\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if skill[i]+skill[j] == total:\n",
    "                res+=skill[i]*skill[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "                continue\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        count=int((len(skill)+1)/2)\n",
    "        skill_tep=sorted(skill)\n",
    "        skillnum=min(skill)+max(skill)\n",
    "        ans=0\n",
    "        for i in range(count):\n",
    "            if skill_tep[i]+ skill_tep[len(skill)-1-i]!=skillnum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans=ans+skill_tep[i]*skill_tep[len(skill)-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\"\"\"\n",
    "1 2 3 3 4 5\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n = len(skill)\n",
    "        skill.sort()\n",
    "\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        answer = 0\n",
    "        pre = skill[left] + skill[right]\n",
    "        while left < right:\n",
    "            s = skill[left] + skill[right]\n",
    "            if s == pre:\n",
    "                answer += skill[left] * skill[right]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans = 0\n",
    "        c = skill[0] + skill[-1]\n",
    "        n = len(skill)\n",
    "        for i in range(n>>1):\n",
    "            if skill[i] + skill[n-i-1] != c:\n",
    "                return -1\n",
    "            ans += skill[i] * skill[n-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        total, m = sum(skill), len(skill) // 2\n",
    "        if total % m: return -1\n",
    "        ans, s = 0, total // m\n",
    "        cnt = Counter(skill)\n",
    "        for x, c in cnt.items():\n",
    "            if c != cnt[s - x]: return -1\n",
    "            ans += c * x * (s - x)\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        res=0\n",
    "        s=skill[0]+skill[-1]\n",
    "        for i in range(len(skill)//2):\n",
    "            x,y=skill[i],skill[-1-i]\n",
    "            if s!=x+y:\n",
    "                return -1\n",
    "            res+=x*y\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        sort_skill = sorted(skill)\n",
    "        tmp = sort_skill[0] + sort_skill[-1]\n",
    "        n = len(skill)\n",
    "        out = 0\n",
    "        for i in range (n // 2):\n",
    "            if sort_skill[i] + sort_skill[n-i-1] != tmp:\n",
    "                return -1\n",
    "            out += sort_skill[i] * sort_skill[n-i-1]\n",
    "        return out "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      skill.sort()\n",
    "      n=len(skill)\n",
    "      ans=0\n",
    "      tot=skill[0]+skill[-1]\n",
    "      for i in range(n//2):\n",
    "        if skill[i]+skill[n-i-1]!=tot:\n",
    "          return -1\n",
    "        ans+=skill[i]*skill[n-i-1]\n",
    "      return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        total , m = sum(skill),len(skill)//2\n",
    "        if total % m : return -1 \n",
    "        ans , s = 0 , total //m\n",
    "        cnt = Counter(skill)\n",
    "        for x , c in cnt.items():\n",
    "            if c != cnt[s-x]:\n",
    "                return -1 \n",
    "            ans += c * x * (s-x)\n",
    "        return ans // 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        s=0\n",
    "        d=defaultdict(int)\n",
    "        for sk in skill:\n",
    "            s+=sk\n",
    "            d[sk]+=1\n",
    "        n=len(skill)>>1\n",
    "        if s%n!=0:\n",
    "            return -1\n",
    "        ans=0\n",
    "        s//=n\n",
    "        for sk in d.keys():\n",
    "            if d[s-sk]!=d[sk]:\n",
    "                return -1\n",
    "            ans+=d[sk]*sk*(s-sk)\n",
    "        return ans>>1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        leng=len(skill)\n",
    "        count=(leng+1)//2\n",
    "        skill.sort()\n",
    "        skillnum=min(skill)+max(skill)\n",
    "        ans=0\n",
    "        for i in range(count):\n",
    "            if skill[i]+ skill[leng-1-i]!=skillnum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans=ans+skill[i]*skill[leng-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans = 0\n",
    "        cnt = skill[-1] + skill[0]\n",
    "        l, r = 0, len(skill) - 1\n",
    "        while l < r:\n",
    "            if skill[l] + skill[r] != cnt: return -1\n",
    "            ans += skill[l] * skill[r]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n=len(skill)\n",
    "        skill.sort()\n",
    "        target=skill[0]+skill[-1]\n",
    "        l,r=1,n-2\n",
    "        while l<r:\n",
    "            if skill[l]+skill[r]!=target:\n",
    "                return -1\n",
    "            l+=1\n",
    "            r-=1\n",
    "        ans=0\n",
    "        l,r=0,n-1\n",
    "        while l<r:\n",
    "            ans+=skill[l]*skill[r]\n",
    "            l+=1\n",
    "            r-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        sum = skill[0] + skill[-1]\n",
    "        ans = skill[0] * skill[-1]\n",
    "        for i in range(1, len(skill) // 2):\n",
    "            if skill[i] + skill[-i - 1] != sum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans += skill[i] * skill[-i - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        res=0\n",
    "        skill.sort()\n",
    "        score=skill[0]+skill[-1]\n",
    "        n=len(skill)\n",
    "        for i in range(len(skill)//2):\n",
    "            cur_score=skill[i]+skill[n-i-1]\n",
    "            if score!=cur_score:\n",
    "                return -1\n",
    "            res+=skill[i]*skill[n-i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        leng=len(skill)\n",
    "        count=(leng+1)//2\n",
    "        skill.sort()\n",
    "        skillnum=min(skill)+max(skill)\n",
    "        ans=0\n",
    "        for i in range(count):\n",
    "            if skill[i]+ skill[leng-1-i]!=skillnum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans=ans+skill[i]*skill[leng-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        left = 0\n",
    "        right = len(skill)-1\n",
    "        temp = skill[left]+skill[right]\n",
    "        res = 0\n",
    "        while left < right:\n",
    "            if skill[left]+skill[right]==temp:\n",
    "                res += skill[left]*skill[right]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                return -1\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n = len(skill)//2\n",
    "        和 = sum(skill)\n",
    "        if 和%n:\n",
    "            return -1\n",
    "        和 //= n\n",
    "        字典 = dict()\n",
    "        for i in skill:\n",
    "            字典[i] = 字典.get(i, 0) + 1\n",
    "        if 和%2 == 0 and 和//2 in 字典:\n",
    "            if 字典[和//2] % 2 == 1:\n",
    "                return -1\n",
    "            else:\n",
    "                字典[和//2] //= 2\n",
    "        化学反应和 = 0\n",
    "        for i in 字典:\n",
    "            x = 和-i\n",
    "            if x not in 字典 or 字典[i] != 字典[x]:\n",
    "                return -1\n",
    "            化学反应和 += i*x*字典[i] \n",
    "            字典[x] = 0\n",
    "            字典[i] = 0\n",
    "        return 化学反应和"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        check = skill[0] + skill[-1]\n",
    "        ans = 0\n",
    "        \n",
    "\n",
    "        for i in range (len(skill)//2):\n",
    "            x,y = skill[i],skill[len(skill)-1-i]\n",
    "            if x + y != check:return -1\n",
    "            else:\n",
    "                ans += x *y\n",
    "            \n",
    "        return ans \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n = len(skill)\n",
    "        total = sum(skill)\n",
    "        cnt = n//2\n",
    "        target = total//cnt\n",
    "        ans = 0\n",
    "        record = Counter(skill)\n",
    "        for k in record:\n",
    "            if k >= target:\n",
    "                return -1\n",
    "            v = record[k]\n",
    "            if v == 0:\n",
    "                continue\n",
    "            t = target-k\n",
    "            if t == k:\n",
    "                if v&1:\n",
    "                    return -1\n",
    "                ans += k*k*(v//2)\n",
    "            else:\n",
    "                if record[t] < v:\n",
    "                    return -1\n",
    "                record[t] -= v\n",
    "                ans += k*t*v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        n = len(skill)\n",
    "        s = skill[-1]+skill[0]\n",
    "        if not all(skill[x]+skill[n-1-x]==s for x in range(n//2)):\n",
    "            return -1\n",
    "        ans = 0\n",
    "        for x in range(n//2):\n",
    "            ans += skill[x]*skill[n-1-x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s:\n",
    "                return -1\n",
    "            ans += x * y\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        ans= 0 \n",
    "        sum_ = sum(skill)\n",
    "        n = len(skill)\n",
    "        group_sum = sum_*2 // n\n",
    "        counter = Counter(skill)\n",
    "        for k,v in counter.items() :\n",
    "            if v != counter[group_sum-k]:\n",
    "                return -1 \n",
    "            else :\n",
    "                ans += k * (group_sum-k)*v \n",
    "        return ans//2 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "\n",
    "        n = len(skill)\n",
    "        if n == 2:\n",
    "            return skill[0] * skill[1]\n",
    "\n",
    "        # 团队技能点之和\n",
    "        tn = sum(skill) * 2 / n\n",
    "\n",
    "        # 团队技能点之和是整数\n",
    "        if tn%1 != 0:\n",
    "            return -1\n",
    "\n",
    "        # 每一对的技能点\n",
    "        res = []\n",
    "        # 每一对出现的次数\n",
    "        rets = []\n",
    "        skill.sort()\n",
    "        # 总共出现的技能点数和次数\n",
    "        td = Counter(skill)\n",
    "        # 总共出现的技能点数\n",
    "        tl = list(td.keys())\n",
    "\n",
    "        def getResList(tl):\n",
    "            lent = len(tl)\n",
    "            # 技能点数列表为空，直接返回\n",
    "            if lent == 0:\n",
    "                return\n",
    "            # 技能点数列表为1个，判断这个数*2是否=团队的技能点之和\n",
    "            elif lent == 1:\n",
    "                # 等于团队的技能点之和，保存数值和次数\n",
    "                # 否则直接返回\n",
    "                if tl[0] * 2 == tn:\n",
    "                    res.append([tl[0], tl[0]])\n",
    "                    rets.append(td[tl[0]]/2)\n",
    "                    tl.pop()\n",
    "                    return\n",
    "                else:\n",
    "                    return\n",
    "\n",
    "            # 最大的数与最小的树开始遍历\n",
    "            # 最后一个数\n",
    "            r = tl[-1]\n",
    "            for i in range(lent-1):\n",
    "                # 和等于团队的技能点之和\n",
    "                if r + tl[i] == tn:\n",
    "                    # 数的个数是否相等\n",
    "                    if td[tl[i]] == td[r]:\n",
    "                        # 个数相等，保存数字\n",
    "                        res.append([tl[i], r])\n",
    "                        # 保存数字的个数\n",
    "                        rets.append(td[r])\n",
    "                        # 将数字去除，继续递归\n",
    "                        tl.pop(-1)\n",
    "                        tl.pop(i)\n",
    "                        # 继续递归\n",
    "                        getResList(tl)\n",
    "                        return\n",
    "            return\n",
    "        getResList(tl)\n",
    "        \n",
    "        if sum(rets) != n/2:\n",
    "            return -1\n",
    "        \n",
    "        return int(sum([res[i][0]*res[i][1]*rets[i] for i in range(len(rets))]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "\n",
    "        n = len(skill)\n",
    "        if n == 2:\n",
    "            return skill[0] * skill[1]\n",
    "\n",
    "        # 团队技能点之和\n",
    "        tn = sum(skill) * 2 / n\n",
    "\n",
    "        # 团队技能点之和是整数\n",
    "        if tn%1 != 0:\n",
    "            return -1\n",
    "\n",
    "        res = []\n",
    "        rets = []\n",
    "        skill.sort()\n",
    "        td = Counter(skill)\n",
    "        tl = list(td.keys())\n",
    "\n",
    "        def getResList(tl):\n",
    "            lent = len(tl)\n",
    "            if lent == 0:\n",
    "                return\n",
    "            elif lent == 1:\n",
    "                if tl[0] * 2 == tn:\n",
    "                    res.append([tl[0], tl[0]])\n",
    "                    rets.append(td[tl[0]]/2)\n",
    "                    tl.pop()\n",
    "                    return\n",
    "\n",
    "            # 最后一个数\n",
    "            r = tl[-1]\n",
    "            for i in range(lent-1):\n",
    "                # 和等于团队的技能点之和\n",
    "                if r + tl[i] == tn:\n",
    "                    # 数的个数是否相等\n",
    "                    if td[tl[i]] == td[r]:\n",
    "                        # 个数相等，保存数字\n",
    "                        res.append([tl[i], r])\n",
    "                        # 保存数字的个数\n",
    "                        rets.append(td[r])\n",
    "                        # 将数字去除，继续递归\n",
    "                        tl.pop(-1)\n",
    "                        tl.pop(i)\n",
    "                        # 继续递归\n",
    "                        getResList(tl)\n",
    "                        return\n",
    "            return\n",
    "        getResList(tl)\n",
    "        \n",
    "        if sum(rets) != n/2:\n",
    "            return -1\n",
    "        \n",
    "        return int(sum([res[i][0]*res[i][1]*rets[i] for i in range(len(rets))]))\n",
    "\n",
    "            \n",
    "\n",
    "        # def getResList(temp):\n",
    "        #     lt = len(temp)\n",
    "        #     if lt == 0:\n",
    "        #         return\n",
    "        #     # 最后一个数\n",
    "        #     r = temp[-1]\n",
    "        #     for i in range(lt - 1 ):\n",
    "        #         if temp[i] + r == tn:\n",
    "        #             res.append([temp[i], r])\n",
    "        #             temp.pop(-1)\n",
    "        #             temp.pop(i)\n",
    "        #             getResList(temp)\n",
    "        #             return\n",
    "        #     return\n",
    "        # getResList(t)\n",
    "        \n",
    "        # if len(res) != n/2:\n",
    "        #     return -1\n",
    "\n",
    "        # return sum(r[0]*r[1] for r in res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        l = collections.deque(sorted(skill))\n",
    "        target, res = sum(skill)*2//len(skill), 0\n",
    "        while l:\n",
    "            a, b = l.pop(), l.popleft()\n",
    "            if a+b==target: res+=a*b\n",
    "            else: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n=len(skill)\n",
    "        s,group=sum(skill)//(n//2),[[-1,-1]*(n//2)]\n",
    "        c=Counter(skill)\n",
    "        ret=0\n",
    "        print(c)\n",
    "        for k,v in c.items():\n",
    "            print(k,v)\n",
    "            if k+k==s:\n",
    "                ret+=(v//2)*(k*k)\n",
    "                continue\n",
    "            if c[s-k]>=v:\n",
    "                c[k]-=v\n",
    "                c[s-k]-=v\n",
    "                ret+=v*k*(s-k)\n",
    "            else:\n",
    "                return -1\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, a: List[int]) -> int:\n",
    "        n=len(a)\n",
    "        s=sum(a)\n",
    "        if s%(n//2)!=0:\n",
    "            return -1\n",
    "        s//=n//2\n",
    "        ans=0\n",
    "        from sortedcontainers import SortedList\n",
    "        u=SortedList(a)\n",
    "        for i in a:\n",
    "            if i not in u:\n",
    "                continue\n",
    "            u.remove(i)\n",
    "            if s-i not in u:\n",
    "                return -1\n",
    "            u.remove(s-i)\n",
    "            ans+=i*(s-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, S: List[int]) -> int:\n",
    "        A, B = sorted(S), sorted(S, reverse=True)\n",
    "        return sum(a * b for a, b in zip(A, B)) >> 1 if all(A[0] + B[0] == a + b for a, b in zip(A, B)) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n = len(skill)\n",
    "        m = n // 2\n",
    "        skill.sort()\n",
    "        arr = [None] * m\n",
    "        arr[0] = (skill[0], skill[-1], skill[0] * skill[-1])\n",
    "        l, r = 1, n - 2\n",
    "        index = skill[0] + skill[-1]\n",
    "        total = arr[0][-1]\n",
    "        flag = False\n",
    "        while l < r: \n",
    "            if skill[l] + skill[r] != index:\n",
    "                flag = True\n",
    "                break\n",
    "            arr[l] = (skill[l], skill[r], skill[l] * skill[r])\n",
    "            total += arr[l][-1]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        if flag: return -1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        b=-1\n",
    "        skill.sort(reverse=False)\n",
    "\n",
    "        s = len(skill) / 2\n",
    "        # 获取数组长度 看看能分成几组\n",
    "\n",
    "        # 中位数相加\n",
    "        huaxue=skill[int(s)]+skill[int(s)-1]\n",
    "        # 得出化学反应\n",
    "\n",
    "        xc=[]\n",
    "        xin=[]\n",
    "        # xin拿来判断 是否和原本的列表一致 不一致给-1\n",
    "        for i in range(0,int(s)):\n",
    "            for j in range(len(skill)-i-1,len(skill)-i-2,-1):\n",
    "                if huaxue==skill[i]+skill[j]:\n",
    "                    xin.append(skill[i])\n",
    "                    xin.append(skill[j])\n",
    "                    xiangc=skill[i]*skill[j]\n",
    "                    xc.append(xiangc)\n",
    "\n",
    "        # 这是最终反应之和\n",
    "\n",
    "        # 排序一致 # xin拿来判断 是否和原本的列表一致 不一致给-1\n",
    "        xin.sort(reverse=False)\n",
    "        if xin==skill:\n",
    "            return sum(xc)\n",
    "        else:\n",
    "            return b\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
